НУЛП, ІКНІ, САПР
Тема
оцінка
підпис
АЛГОРИТМ РІШЕННЯ ЗАДАЧІ ЛИСТОНОШІ
№ залікової:
Дискретні моделі в САПР
Викладач:
Мета роботи : метою даної лабораторної роботи є вивчення алгоритмів рішення задачі листоноші.
Короткі теоретичні відомості :
Задача листоноші може бути сформульована в термінах теорії графів. Для цього побудуємо граф G = (X , E), в якому кожна дуга відповідає вулиці в маршруті руху листоноші, а кожна вершина - стик двох вулиць. Ця задача являє собою задачу пошуку найкоротшого маршруту, який включає кожне ребро хоча б один раз і закінчується у початковій вершині руху.
Ейлеревим циклом в графі називається шлях, який починається і закінчується в тій самій вершині, при чому всі ребра графа проходяться тільки один раз. Ейлеревим шляхом називається шлях, який починається в вершині А, а закінчується в вершині Б, і всі ребра проходяться лише по одному разу.
Теорема 1.
Якщо у графа всі вершини мають парну степінь, то цей граф Ейлерів, тобто має Ейлерів цикл.
Теорема 2 .
Якщо в графі існує Ейлерів шлях, то це означає, що в нього є строго дві непарні вершини. При чому шлях починається в одній з них, а закінчується в іншій.
Задача листоноші для неорієнтованого графа G(Х,E) - це задача для графа, в якому ребра
можна проходити в будь-якому з двох напрямків. Необхідно розгянути окремо наступні два випадки :
Випадок 1 : Граф G парний.
Випадок 2 : Граф G непарний.
Випадок 1 : Якщо граф парний, то оптимальним рішенням задачі є ейлеровий маршрут. В цьому випадку листоноша не повинен обходити більше одного разу будь-яку вулицю, в даному випадку ребро графа. Як найти на графі G ейлеровий маршрут, в якому “S” - початкова вершина? Для цього необхідно пройти будь-яке ребро (S,x) інцидентне вершині “S”, а потім ще невикористане ребро, інцидентне вершині “x”. Кожен раз, коли листоноша приходить в деяку вершину, є невикористане ребро по якому листоноша покидає цю вершину. Дуги, по яким здійснений обхід, створюють цикл С1 . Якщо в цикл С1 ввійшли всі ребра графа G, то С1 є ейлеровим маршрутом (оптимальним для задачі). В іншому випадку треба створити цикл С2, який складається з невикористаних ребер і який починається з невикористаного ребра. Створення циклів С3, С4,..., продовжується доти, доки не будуть використані всі ребра графа. Далі треба об’єднати цикли С1,С2,С3,... в один цикл С, який містить всі ребра графа G. В цикл C кожне ребро графа входить лише один раз, і тому він є оптимальним рішенням задачі листоноші.Два цикла C1 і C2 можуть бути з’єднані тільки тоді, коли вони мають спільну вершину “х”. Для з’єднання двох таких циклів необхідно вибрати в якості початкового довільне ребро циклу С1 і рухатися вздовж його ребер до вершини “х”. Далі потрібно пройти всі ребра циклу С2 і повернутися у вершину “х”.На кінець, потрібно продовжити прохід ребер цикла С1 до повернення. Реалізація алгоритму (Java) :
public void printEulerTour() {
int vertex = 1;
/*
Визначення непарної вершини
*/
if (oddDegreeVertex() != -1) {
vertex = oddDegreeVertex();
}
/*
Вивід ейлерового шляху
*/
printEulerTourUtil(vertex);
return;
}
/*
Перевірка на непарність вершини,-1 - парна, інше - непарна
*/
public int oddDegreeVertex() {
int vertex = -1;
for (int node = 1; node <= numberOfNodes; node++) {
/*
Якщо залишок від ділення на 2 не дорівнює 0
тоді вершина має непарний степінь.
*/
if ((degree(node) % 2) != 0) {
vertex = node;
break;
}
}
return vertex;
}
/*
Обчислення степеня вершини
*/
public int degree(int vertex) {
int degree = 0;
for (int destinationvertex = 1; destinationvertex <= numberOfNodes; destinationvertex++) {
if (adjacencyMatrix[vertex][destinationvertex] == 1
|...
